home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / bool / bv.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  8.3 KB  |  364 lines
  1. /***************************  bv-bool-ops.c  *****************************
  2.  
  3.   Purpose:    Implementation of boolean operations as bit vectors.
  4.  
  5.   Provenance:    Written and tested by S. Wartik, April 1991.
  6.  
  7.   Notes:    None.
  8.  
  9. **/
  10.  
  11. #include    "bv.h"
  12.  
  13. static boolean error_occurred;    /* TRUE iff an error occurred on the    */
  14.                 /* last call to a boolean operator.    */
  15.  
  16. /**************************************************************************
  17.  
  18.       Create(lower, upper, s)
  19.  
  20.   Returns:    void
  21.  
  22.   Purpose:    Create a set capable of containing values in the range
  23.           [lower,upper].
  24.  
  25.   Plan:        Set the values of "s" to the parameters.
  26.  
  27.   Notes:    This routine must be called before any of the other
  28.           routines (save error_occurred()) will work.
  29.  
  30. **/
  31.  
  32. void Create(lower, upper, s)
  33.     int     lower, upper;    /* in: gives the set's domain.    */
  34.     set     *s;            /* out: the set.        */
  35. {
  36.     if ( lower > upper || (upper - lower) >= MAX_ELEMENTS ) {
  37.         error_occurred = TRUE;
  38.         return;
  39.     }
  40.     s->lower = lower;
  41.     s->upper = upper;
  42.     error_occurred = FALSE;
  43. }
  44.  
  45. /**************************************************************************
  46.  
  47.       Clear(s)
  48.  
  49.   Returns:    void
  50.  
  51.   Purpose:    Indicate that set s is empty.
  52.  
  53.   Plan:        Set all bits of s to 0.
  54.  
  55.   Notes:    The Create() function does not automatically clear
  56.           a set; this routine must be called to do so.
  57.  
  58. **/
  59.  
  60. void Clear(s)
  61.         set     *s;    /* out: the set to be cleared. */
  62. {
  63.     register int    i, Number_Of_Bytes;
  64.     Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;
  65.     for ( i = 0; i < Number_Of_Bytes; i++ )
  66.         s->bits[i] = 0;
  67.     error_occurred = FALSE;
  68. }
  69.  
  70. /**************************************************************************
  71.  
  72.       Insert(s, e)
  73.  
  74.   Returns:    void
  75.  
  76.   Purpose:    Insert element e into set s.
  77.  
  78.   Plan:        Determine the bit in s to which e corresponds, and set
  79.           that bit to 1.
  80.  
  81.   Notes:    e may already be in s.
  82.  
  83. **/
  84.  
  85. void Insert(s, e)
  86.     set             *s;    /* in out: the set to receive the element. */
  87.     elementType     e;    /* in: the element to be inserted.       */
  88. {
  89.     if ( e < s->lower || e > s->upper ) {
  90.         error_occurred = TRUE;
  91.         return;
  92.     }
  93.     s->bits[(e-s->lower)/WORDSIZE] |= 01 << ((e-s->lower)%WORDSIZE);
  94.     error_occurred = FALSE;
  95. }
  96.  
  97. /**************************************************************************
  98.  
  99.       Delete(s, e)
  100.  
  101.   Returns:    void
  102.  
  103.   Purpose:    Delete element e from set s.
  104.  
  105.   Plan:        Determine the bit in s to which e corresponds, and set that
  106.           bit to 0.
  107.  
  108.   Notes:    e doesn't have to be in s.
  109.  
  110. **/
  111.  
  112. void Delete(s, e)
  113.     set             *s;    /* in out: the set from which to delete. */
  114.     elementType     e;    /* in: the element to delete.         */
  115. {
  116.     if ( e < s->lower || e > s->upper ) {
  117.         error_occurred = TRUE;
  118.         return;
  119.     }
  120.     s->bits[(e-s->lower)/WORDSIZE] &= ~(01 << ((e-s->lower)%WORDSIZE));
  121.     error_occurred = FALSE;
  122. }
  123.  
  124. /**************************************************************************
  125.  
  126.       Empty(s)
  127.  
  128.   Returns:    boolean
  129.  
  130.   Purpose:    Determine whether a set is empty: return TRUE iff it is.
  131.  
  132.   Plan:        Any non-zero bit indicates the set is not empty; test
  133.           for that.
  134.  
  135.   Notes:    None.
  136.  
  137. **/
  138.  
  139. boolean Empty(s)
  140.     set     *s;        /* in: the set whose emptiness is to be checked. */
  141. {
  142.     register int    i, Number_Of_Bytes;
  143.     error_occurred = FALSE;
  144.     Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;
  145.     for ( i = 0; i < Number_Of_Bytes; i++ )
  146.         if ( s->bits[i] )
  147.             return FALSE;
  148.     return TRUE;
  149. }
  150.  
  151. /**************************************************************************
  152.  
  153.       Member(s, e)
  154.  
  155.   Returns:    boolean
  156.  
  157.   Purpose:    Determine if e is a member of s: return TRUE iff it is.
  158.  
  159.   Plan:        Check the bit to which e corresponds.
  160.  
  161.   Notes:    None.
  162.  
  163. **/
  164.  
  165. boolean Member(s, e)
  166.     set     *s;
  167.     elementType     e;
  168. {
  169.     if ( error_occurred = (e < s->lower || e > s->upper) )
  170.         return FALSE;
  171.     return (s->bits[(e - s->lower)/WORDSIZE] >> (e - s->lower)%WORDSIZE) & 01;
  172. }
  173.  
  174. /* The following macro tests whether two sets have an equivalent domain --
  175.  * i.e., bounds.  It is only possible to perform the boolean operations
  176.  * on equivalent sets.
  177.  */
  178. #define equivalent(s1, s2) \
  179.   ((s1)->lower==(s2)->lower && (s1)->upper==(s2)->upper)
  180.  
  181. /**************************************************************************
  182.  
  183.       Unite(s1, s2, s3)
  184.  
  185.   Returns:    void
  186.  
  187.   Purpose:    Return in s3 the union of sets s1 and s2.
  188.  
  189.   Plan:        Use the bitwise OR operator to construct the union
  190.           of each set of words in s1 and s2.
  191.  
  192.   Notes:    None.
  193.  
  194. **/
  195.  
  196. void Unite(s1, s2, s3)
  197.     set     *s1, *s2;    /* in: the sets to be united.   */
  198.     set     *s3;    /* out: the union of s1 and s2. */
  199. {
  200.     register int    i, Number_Of_Bytes;
  201.  
  202.     if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
  203.         error_occurred = TRUE;
  204.         return;
  205.     }
  206.  
  207.     Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
  208.     for ( i = 0 ; i < Number_Of_Bytes; i++ )
  209.         s3->bits[i] = (s1->bits[i] | s2->bits[i]);
  210.     error_occurred = FALSE;
  211. }
  212.  
  213. /**************************************************************************
  214.  
  215.       Intersect(s1, s2, s3)
  216.  
  217.   Returns:    void
  218.  
  219.   Purpose:    Return in s3 the intersection of s1 and s2.
  220.  
  221.   Plan:        Use the bitwise AND operator to construct the intersection
  222.           of s1 and s2.
  223.  
  224.   Notes:    None.
  225.  
  226. **/
  227. void Intersect(s1, s2, s3)
  228.     set     *s1, *s2;        /* in: the sets to be intersected.     */
  229.     set     *s3;        /* out: the intersection of s1 and s2. */
  230. {
  231.     register int    i, Number_Of_Bytes;
  232.  
  233.     if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
  234.         error_occurred = TRUE;
  235.         return;
  236.     }
  237.  
  238.     Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
  239.     for ( i = 0 ; i < Number_Of_Bytes; i++ )
  240.         s3->bits[i] = (s1->bits[i] & s2->bits[i]);
  241.     error_occurred = FALSE;
  242. }
  243.  
  244. /**************************************************************************
  245.  
  246.       Subtract(s1, s2, s3)
  247.  
  248.   Returns:    void
  249.  
  250.   Purpose:    Return in s3 the difference between s1 and s2 (i.e., s1-s2).
  251.  
  252.   Plan:        Use the formula (A&~B) on each corresponding pair of
  253.           words in s1 and s2.
  254.  
  255.   Notes:    None.
  256.  
  257. **/
  258.  
  259. void Subtract(s1, s2, s3)
  260.     set     *s1, *s2;    /* in: the sets to be subtracted.      */
  261.     set     *s3;    /* out: the difference between s1 and s2. */
  262. {
  263.     register int    i, Number_Of_Bytes;
  264.  
  265.     if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
  266.         error_occurred = TRUE;
  267.         return;
  268.     }
  269.  
  270.     Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
  271.     for ( i = 0 ; i < Number_Of_Bytes; i++ )
  272.         s3->bits[i] = s1->bits[i] & ~(s2->bits[i]);
  273.     error_occurred = FALSE;
  274. }
  275.  
  276. /**************************************************************************
  277.  
  278.       Copy(source, destination)
  279.  
  280.   Returns:    void
  281.  
  282.   Purpose:    Create a copy of a set.
  283.  
  284.   Plan:        Trivial.
  285.  
  286.   Notes:    None.
  287.  
  288. **/
  289.  
  290. void Copy(source, destination)
  291.     set *source,        /* in: the set to be copied. */
  292.     *destination;        /* out: a copy of "source".  */
  293. {
  294.     register int       i;
  295.  
  296.     if ( ! equivalent(source, destination) ) {
  297.         error_occurred = TRUE;
  298.         return;
  299.     }
  300.     for ( i = 0; i < MAX_ELEMENTS/WORDSIZE; i++ )
  301.         destination->bits[i] = source->bits[i];
  302.     error_occurred = FALSE;
  303. }
  304.  
  305. /**************************************************************************
  306.  
  307.       Iterate(s, f)
  308.  
  309.   Returns:    void
  310.  
  311.   Purpose:    Perform some application-defined function f on each element
  312.           of set s.  The function f() should be of the form:
  313.  
  314.             boolean f(e)
  315.                 elementType    e;
  316.  
  317.         The iteration will continue as long as more elements
  318.         remain in the set and f() returns TRUE.
  319.  
  320.   Plan:        
  321.  
  322.   Notes:    There is no guaranteed order in which the elements are
  323.           passed to f().
  324.  
  325. **/
  326.  
  327. void Iterate(s, f)
  328.     set     *s;        /* in: the set to iterate through.        */
  329.     boolean (*f)();    /* in: the function to perform on the elements. */
  330. {
  331.     register int    i, j, Number_Of_Bytes;
  332.     Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;
  333.  
  334.     error_occurred = FALSE;
  335.         
  336.     for ( i = 0; i < Number_Of_Bytes; i++ )
  337.         for ( j = 0; j < WORDSIZE; j++ )
  338.         if ( (s->bits[i] >> j) % 2 )
  339.         if ( ! (*f)(j + i*WORDSIZE + s->lower) )
  340.             return;
  341. }
  342.  
  343. /**************************************************************************
  344.  
  345.       Error_Occurred()
  346.  
  347.   Returns:    boolean
  348.  
  349.   Purpose:    Indicate whether the last operation could not be
  350.           completed due to some error.
  351.  
  352.   Plan:        The routine's value is the value of the local variable
  353.           "error_occurred".
  354.  
  355.   Notes:    It is the responsibility of each routine to correctly
  356.           set "error_occurred".
  357.  
  358. **/
  359.  
  360. boolean Error_Occurred()
  361. {
  362.     return error_occurred;
  363. }
  364.